package com.lry.basic.algorithm.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * 联通分量相关
 */
public class UndirectedGraphCC {
    private UndirectedGraph graph;
    private int[] visited;
    private int ccCount;//连通分量

    public UndirectedGraphCC(UndirectedGraph graph){
        this.graph = graph;
        visited = new int[graph.vertexNum()];
        for(int i=0;i<visited.length;i++){
            //visited里面-1表示没有访问，0表示第一个联通分量，1表示第二个连通分量，以此类推
            visited[i] = -1;
        }
        for(int v=0;v<graph.vertexNum();v++){
            if(visited[v]==-1){
                dfs(v,ccCount);
                ccCount++;
            }
        }
    }

    private void dfs(int v,int ccId){
        visited[v] = ccId;
        for(int w:graph.adj(v)) {
            if(visited[w]==-1){
                dfs(w,ccId);
            }
        }
    }

    /**
     * 返回所有的连通分量
     * @return
     */
    public List<Integer>[] components(){
        List<Integer>[] res = new ArrayList[ccCount];
        for(int i=0;i<ccCount;i++){
            res[i] = new ArrayList<>();
        }

        for(int v=0;v<graph.vertexNum();v++){
            res[visited[v]].add(v);
        }
        return res;
    }

    public boolean isConnected(int v,int w){
        graph.validateVertex(v);
        graph.validateVertex(w);
        return visited[v]==visited[w];
    }

    public int getCcCount(){return ccCount;}
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for(int v:visited){
            sb.append(v+" ");
        }
        sb.append("\n连通分量:"+ccCount);
        int index = 1;
        for (List<Integer> list:components()){
            sb.append("\n第"+index+++"个连通分量的顶点:");
            for (int v:list) {
                sb.append(v+" ");
            }
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        UndirectedGraphCC graphCC = new UndirectedGraphCC(graph);
        System.out.println(graphCC);
        System.out.println(graphCC.isConnected(0, 6));
        System.out.println(graphCC.isConnected(0, 5));
    }
}
